package find;

import util.Comparator;

import java.util.Arrays;

/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值。要求时间复杂度0(N)，且要求不能用非基于比较的排序。
 * <p>
 * 解法：构建平凡解，使用N + 1桶，将桶内的小间隔都排除掉
 *
 * @author Liaorun
 */
public class MaxGap {

    public static void main(String[] args) {

        int testTime = 100;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;

        for (int i = 0; i < testTime; i++) {
            int[] arr1 = Comparator.generateRandomArray(maxSize, maxValue, false);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            if (maxGap(arr1) != comparator(arr2)) {
                succeed = false;
                break;
            }
        }

        System.out.println(succeed ? "Nice" : "Opps");
    }

    /**
     * 使用系统排序，在计算最大间距，这种笨办法当对数器，检查算法是否正确
     *
     * @param arr2
     * @return
     */
    private static int comparator(int[] arr2) {
        if (arr2 == null || arr2.length < 2) {
            return 0;
        }
        Arrays.sort(arr2);

        int maxGap = 0;
        for (int i = 0; i < arr2.length - 1; i++) {
            maxGap = Math.max(maxGap, arr2[i + 1] - arr2[i]);
        }

        return maxGap;
    }


    public static int maxGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        int length = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        if (min == max) {
            return 0;
        }

        // 记录每个桶内是否有数据
        boolean[] hasNum = new boolean[length + 1];

        // 记录桶中的最大值
        int[] maxs = new int[length + 1];
        // 记录桶中的最小值
        int[] mins = new int[length + 1];
        // 桶号
        int bid = 0;

        for (int i = 0; i < length; i++) {
            // 获取桶的id
            bid = bucket(nums[i], length, min, max);
            // 更新桶的最大值和最小值
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            // 当前桶不在是空桶的flag
            hasNum[bid] = true;
        }

        int res = 0;
        // 上一个非空桶的最大值
        int lastMax = maxs[0];

        for (int i = 1; i <= length; i++) {
            if (hasNum[i]) {
                // res = Math.max(上一个桶的最小值 - 上上个桶的最大值，当前桶的最小值 - 上一个桶的最大值）
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }

        return res;
    }

    private static int bucket(int num, int length, int min, int max) {
        return (num - min) * length / (max - min);
    }

}